import java.util.*;

/**
 * @author LKQ
 * @date 2022/7/14 9:12
 * @description
 */
public class Solution {
    public static void main(String[] args) {
        String[] words = {"apple"};
        WordFilter wordFilter = new WordFilter(words);
        wordFilter.f("a", "e");
    }

}
class WordFilter {
    Trie prefRoot = new Trie();
    Trie sufRoot = new Trie();
    public WordFilter(String[] words) {
        for (int i = 0; i < words.length; i++) {
            insert(words[i], i, prefRoot, true);
            insert(words[i], i, sufRoot, false);
        }
    }

    public int f(String pref, String suff) {
        Trie prefCur = prefRoot;
        Trie sufCur = sufRoot;
        for (int i = 0; i < pref.length(); i++) {
            int index = pref.charAt(i) - 'a';
            if (prefCur.children[index] == null) {
                return -1;
            }
            prefCur = prefCur.children[index];
        }
        for (int i = 0; i < suff.length(); i++) {
            int index = suff.charAt(i) - 'a';
            if (sufCur.children[index] == null) {
                return -1;
            }
            sufCur = sufCur.children[index];
        }
        List<Integer> list = prefCur.list, list1 = sufCur.list;
        int m = list.size(), n = list1.size();
        // 双指针
        for (int i = m - 1, j = n - 1; i >= 0 && j >= 0 ;) {
            if (list.get(i) > list1.get(j)) {
                i--;
            }else if (list.get(i) < list1.get(j)) {
                j--;
            }else {
                return list.get(i);
            }
        }
        return -1;
    }

    public void insert(String a, int idx, Trie node, boolean isPref) {
        int n = a.length();
        node.list.add(idx);
        for (int i = 0; i < n; i++) {
            int index = isPref ? (a.charAt(i) - 'a') :  (a.charAt(n - i - 1) - 'a');
            if (node.children[index] == null) {
                node.children[index] = new Trie();
            }
            node.list.add(idx);
            node = node.children[index];
        }
        node.isEnd = true;
    }
}
class Trie {
    Trie[] children;
    boolean isEnd;
    List<Integer> list;
    public Trie() {
        children = new Trie[26];
        isEnd = false;
        list = new ArrayList<>();
    }
}
